/*
 *  Copyright 2009 Advanced Industrial Science and Technology (AIST).
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/*! \file
 *  \brief
 *  breadth first search sample
 */ 

#include <thrust/graph/adjacency_list.hpp>
#include <thrust/graph/simple_io.hpp>
#include <thrust/graph/breadth_first_search.hpp>
#include <thrust/device_vector.h>
using namespace thrust;

#include <iostream>
using namespace std;

/*template <typename T, typename Graph>
struct visitor : public bfs_visitor
{
  typedef typename Graph::VertexContainer VertexContainer;
  typedef typename Graph::EdgeContainer EdgeContainer;
  typedef typename VertexContainer::value_type StoredVertex;
  typedef typename EdgeContainer::value_type StoredEdge;

  typedef typename graph_traits<Graph>::kernel_out_edge_iterator kernel_out_edge_iterator;
  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

private:
  T m_time;
  bool* m_flag;
  
  device_ptr<Graph> m_g;  
  device_ptr<StoredVertex> ptr_vertices;
  device_ptr<StoredEdge> ptr_edges;

public:
  __host__
  visitor( bool* flag, Graph* g) 
    : m_time(0), m_flag(flag)
  {
    ptr_vertices  =&(g->get_vertex_container())[0];
    ptr_edges =&(g->get_edge_container())[0];    
    m_g =thrust::device_malloc<Graph>( sizeof(Graph));
  }

  __host__
  ~visitor()
  {                       // XXX : device_free( m_g) is runtime_error. 
    cudaFree( m_g.get()); // thrust bug?
  }

  template <typename Vertex>
  __device__
  void initialize_vertex( Vertex u)
  {
    //m_g.get()->initialize( ptr_vertices, ptr_edges);
    put( vertex_discover_time                 // property map key
	 , *m_g.get()                         // graph
	 , u                                  // vertex
	 , thrust::numeric_limits<size_t>::max() // property map value
	 , thrust::called_from_device_tag()   // called space tag
	 );

    kernel_out_edge_iterator iter, last;
    thrust::tie( iter, last) =out_edges( u, *m_g.get(), thrust::called_from_device_tag());
    for( ; iter !=last; ++iter){
      edge_descriptor e =*iter;
      put( edge_weight
	   , *m_g.get()
	   , e
	   , u
	   , thrust::called_from_device_tag()
	   );
    }
  }

  template <typename Vertex>
  __device__
  void out_step( Vertex u) {
    if(  m_flag[u]){
      put( vertex_discover_time // property map key
	   , *m_g.get()         // graph
	   , u                  // vertex
	   , m_time             // property map value
	   , thrust::called_from_device_tag() // called space tag
	   );
    }
    ++m_time;
  }

  template <typename Vertex>
  __device__
  void discover_vertex( Vertex u) {
    m_flag[u] =true;
  }
  };*/

int
main( int argc, char** argv)
{
  typedef property<vertex_discover_time_t,size_t> VertexProperty;
  typedef property<edge_weight_t,size_t> EdgeProperty;
  typedef adjacency_list<undirectedS,disallow_parallelS
    ,VertexProperty,EdgeProperty
    > graph_t;

  typedef graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
  typedef graph_traits<graph_t>::vertex_iterator vertex_iterator;
  typedef graph_traits<graph_t>::edge_iterator edge_iterator;
  typedef graph_traits<graph_t>::edge_descriptor edge_descriptor;

  std::size_t N =8;
  graph_t g( N);
  
  add_edge( 0, 1, g);
  //add_edge( 7, 0, g);

  std::cout <<g <<std::endl;

  vertex_descriptor s =0;
  //device_vector<bool> flag( N, false);
  //flag[s] =true;
  //visitor<size_t,graph_t> vis( thrust::raw_pointer_cast( &flag[0]), &g);
  
  // breadth first search
  //bfs_visitor vis;
  //breadth_first_search( g, s, vis);

  /*property_map<graph_t,vertex_index_t>::type index 
    =get( vertex_index, g);
  
  property_map<graph_t,vertex_discover_time_t>::type time_stamp 
    =get( vertex_discover_time, g);
  
  for( size_t i =0; i <N; ++i){
    std::cout <<index[i] 
	      <<"(" <<flag[i] <<"), "
	      <<"time stamp: " <<time_stamp[i]
	      <<std::endl;
  }
  
  property_map<graph_t,edge_weight_t>::type weight
    =get( edge_weight, g);
  edge_iterator iter, last;
  thrust::tie( iter, last) =edges( g);
  for( ; iter !=last; ++iter){
    edge_descriptor e =*iter;
    cout <<e <<": weight " <<weight[e] <<endl;
    }*/
  
  return 0;
}
